package IntersectionAndUnion;

/**
 * @author ：wang-ting
 * @Date：2025/6/2 19:59
 */

import java.util.*;
public class IntersectionAndUnion {
    public static ArrayList<Integer> intersection(ArrayList<Integer> list1, ArrayList<Integer> list2) {
        // 使用HashSet提高查找效率
        Set<Integer> set1 = new HashSet<>(list1);
        Set<Integer> set2 = new HashSet<>(list2);

        ArrayList<Integer> result = new ArrayList<>();

        // 遍历较小的集合以提高性能
        Set<Integer> smallerSet = set1.size() < set2.size() ? set1 : set2;
        Set<Integer> largerSet = set1.size() < set2.size() ? set2 : set1;

        for (Integer num : smallerSet) {
            if (largerSet.contains(num)) {
                result.add(num);
            }
        }

        // 排序结果
        Collections.sort(result);
        return result;
    }

    /**
     * 获取两个ArrayList的并集（已排序）
     *
     * @param list1 第一个列表
     * @param list2 第二个列表
     * @return 排序后的并集列表
     */
    public static ArrayList<Integer> union(ArrayList<Integer> list1, ArrayList<Integer> list2) {
        // 使用HashSet自动去重
        Set<Integer> unionSet = new HashSet<>();
        unionSet.addAll(list1);
        unionSet.addAll(list2);

        // 转换为ArrayList并排序
        ArrayList<Integer> result = new ArrayList<>(unionSet);
        Collections.sort(result);
        return result;
    }
}
